package com.javaclimb.music.datastructure;

/**
 * 插入排序：每一步将一个待排序的记录，插入到前面排好序的有序序列中去，直到插完所有的元素为止。
 * 这里以直接插入排序为基础
 * 原始序列：4 2 8 9 5 7 6 1 3  每一步操作都将待排序的元素插入到前面已经排序好的序列中
 *         有序          待排序
 *          4           2 8 9 5 7 6 1 3
 * 第一轮：  2 4          8 9 5 7 6 1 3
 * 第二轮： 2 4 8         9 5 7 6 1 3
 * 第三轮： 2 4 8 9       5 7 6 1 3
 *
 * 第八轮：1 2 4 5 6 7 8 9     3
 *
 */
public class InsertSort {
    public static int[] Sort(int[] arr){
        int j;
        for (int i=1;i< arr.length;i++){
            int t=arr[i];//记录我们要插入的数据
            j=i;
//            要从已经排序的序列最右边的开始比较，找到比其小的数
            while (j>0 && t<arr[j-1]){
                arr[j]=arr[j-1];
                j--;
            }
//            存在比其小的数就插入
            arr[j]=t;
            System.out.println("第"+i+"步排序后:");
            display(arr);
        }
        return arr;
    }

    public static void display(int[] arr){
        for (int i=0;i< arr.length;i++){
            if (i== arr.length-1){
                System.out.println(arr[i] + "  ");
            }else {
                System.out.print(arr[i] + "  ");
            }
        }
    }

    public static void main(String[] args) {
        int[] arr= {4,2,8,9,5,7,6,1,3};
        System.out.println("排序前：");
        InsertSort.display(arr);
        int [] array=InsertSort.Sort(arr);
        System.out.println("排序后：");
        InsertSort.display(array);
    }
}
